package C059;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c03
 * Package: C059
 * Description: https://leetcode.cn/problems/Jf1JuT/description/ 火星字典
 *
 * @Author BCXJ
 * @Create 2025/10/11 17:19
 * @Version 1.0
 * @Since 1.0
 */
public class c03 {
    public static void main(String[] args) {
//        String[] arr = {"wrt","wrf","er","ett","rftt"};
        String[] arr = {"wnlb"};
//        String[] arr = {"abc", "ab"};

        System.out.println(alienOrder(arr));
    }

    public static String alienOrder(String[] words) {
        // 代码健壮性
        if(null == words) {
            return "";
        }

        // 1  入度表并初始化，出现的字母入度设置为0，没有的设置为-1
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                indegree[word.charAt(i) - 'a'] = 0;
            }
        }

        // 2 建图 - 邻接表即可，点就是26个字母（要初始化）, 0 - 26 数字进行表示
        List<List<Integer>> grap = new ArrayList<>(26);
        for(int i = 0; i < 26; i ++) {
            grap.add(new ArrayList<>());
        }

        // 3 遍历字符串，将26字母图建好
        String curStr = "", nextStr = "";
        int len = 0;
        for (int i = 1; i < words.length; i++) {
            curStr = words[i - 1];
            nextStr = words[i];
            len = Math.min(curStr.length(), nextStr.length());
            int j = 0;
            for (; j < len; j++) {
                if(curStr.charAt(j) != nextStr.charAt(j)) { // 待考虑，建议eq
                    grap.get(curStr.charAt(j) - 'a').add(nextStr.charAt(j) - 'a');
                    indegree[nextStr.charAt(j) - 'a'] ++;
                    break;
                }
            }
            // curStr 和 nextStr 前缀一样，但是长度小于 nextStr。 判定规则违规，返回""
            if(j < curStr.length() && j == nextStr.length()) {
                return "";
            }
        }

        // 4 统计入度为0的节点入队列
        int[] queue = new int[26];
        int count = 26; // 含有的字符总数
        int l = 0, r = 0;
        for (int i = 0; i < 26; i++) {
            if(indegree[i] == -1) {
                count --;
            }
            if(indegree[i] == 0) {
                queue[r ++] = i;
            }
        }

        // 5 走拓扑排序
        StringBuilder res = new StringBuilder();
        while(l < r) {
            int curNode = queue[l ++];
            res.append((char) ('a' + curNode)); // 待考虑
            List<Integer> edges = grap.get(curNode);
            for (Integer node : edges) {
                if(-- indegree[node] == 0) {
                    queue[r ++] = node;
                }
            }
            count --;
        }

        return count == 0 ? res.toString() : "";
    }


}
